Graph / Bipartite graph (Bibtex)

P503: Enumerate all maximal connected induced bipartite subgraphs in a graph

Input:

A graph $G = (V, E)$.

Output:

All maximal connected induced bipartite graphs in $G$.

Complexity:

$O(mn)$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)

P504: Enumerate all maximal induced bipartite subgraphs in a graph

Input:

A graph $G = (V, E)$.

Output:

All maximal induced bipartite subgraphs in $G$.

Complexity:

$O(|V|(|E| +|V| \alpha(|V|)))$ delay, where $\alpha(\cdot)$ is the inverse of Ackerman function.

Comment:

Exponential space. Proximity search. A solution may be disconnected.

Reference:

[Conte2019] (Bibtex)

P505: Enumerate all maximal edge bipartite subgraphs in a graph

Input:

A graph $G = (V, E)$.

Output:

All maximal edge bipartite subgraphs in $G$.

Complexity:

$O(|E|^3)$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)